\usepackage{listings}
\lstset{language=Java,
        basicstyle=\small}

\usepackage{graphicx}
\usepackage{hyperref}
\mode<article>{\usepackage{fullpage}}

\hypersetup{
  colorlinks=true,
  urlcolor=blue,
  linkcolor=black
}

\title{Lecture Ten -- Priority Queues}
\author{Matt Bone}
\date{\today}

\begin{document}

\mode<article>{\maketitle}
\tableofcontents
\mode<article>{\pagebreak}
\mode<presentation>{\frame{\titlepage}}
\mode<article>{\setlength{\parskip}{.25cm}}
\mode<all>{\bibliographystyle{abbrvnat}}

\section{Priority Queues}

\subsection{Priorities}
As with most of our data structures, priority queues have two
interesting operations, insert and remove.  In a priority queue, every
element has an associated \emph{priority}.  Items are removed
according to their priority.

In a min-heap, the remove removes the object with the lowest priority.
In a max-heap, the remove removes the object with the highest
priority.

Though they are essentially the same (you can convert one to the other
by multiplying all priorities by one), for simplicity's sake will we
only consider min-heaps for the duration of these notes.

\subsection{Applications}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Priority Queue Applications}}
  \begin{itemize}
    \item Operating systems scheduler
    \item Thread workpools
    \item Distributed computing resource scheduling
  \end{itemize}
\end{frame}
Pretty much when you don't want a ``fair'' first-come-first-served
approach and instead classify things on some quantity, you would use a
priority queue.

\subsection{A Very Simple Implementation: Lists}
It is quite easy to create a naive implementation of a priority queue
using some form of a list:
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Priority Queue: List Implementation}}
  \begin{itemize}
    \item Insert at end of the list
    \item Traverse the entire list each time to find the lowest priority.
  \end{itemize}
\end{frame}
Notice that this implementation runs at $O(n)$.  If the item with the
lowest priority is always stored at the end of the list, this
implementation will perform quite poorly.  Notice, however, that if we
have an already sorted linked list, we have a simple constant time
implementation (however, this is quite an assumption, and we mask ask
ourselves how the list was sorted in the first place).

\subsection{A More Sophisticated Implementation: Binary Search Tree}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Priority Queue: Binary Search Tree Implementation}}
  \begin{center}\includegraphics[width=6cm]{sample_binary_search_tree}\end{center}
\end{frame}

We can use a binary search tree to implement the priority queue.  The
minimum item in the queue is the item farthest to the left.  It would
be trivial to write a recursive algorithm to find, and return/remove
this item.

Using the strategies to keep the tree busy (AVL, splay, red/black,
etc.), we we can get an $O(log(N))$ running time for both insertion and
removal.  Yet a binary search tree actually contains more information
than we need and is overkill.


\section{Heaps}
Though we have the tools to create the previous two implementations, and
while the second performs adequately, priority queues are usually implemented
with a different data structure, the heap.

A heap, like a binary tree, is a tree structure.  As with our previous
tree definitions and our revised list definition, we will define heaps
recursively.

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Heaps: Definition}}
  A \emph{heap} is:
  \begin{itemize}
    \item A complete binary tree 
    \item Root is smallest (or largest) element in the tree
    \item Every child node is also a heap
  \end{itemize}
\end{frame}

We can look at one possible heap made up of the same nodes as the 
previous binary search tree:
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Heaps: A Picture}}
  \begin{center}\includegraphics[width=6cm]{sample_heap}\end{center}
\end{frame}
Notice that the conditions for a binary tree are much looser.  Given
the set of nodes shown above, we can think of many valid heaps (this
is not the case for a BST).  For all of these valid heaps, however,
$17$ is the root element.

\subsubsection{Heap Insert}
Remember that a heap is a complete tree, and after an insertion it
must also be complete.  So, the easiest spot to insert a node is in
the one spot that would allow the new tree to still be a complete
tree.

However, after the initial insertion, the properties of the heap may
not hold.  We must fix the heap.  For an insertion, this is done by
percolating up.

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Heaps: Percolate Up}}
  To \emph{percolate up}, we check to see if a node is less than it's parent.
  if it is not, we swap the two.  This process continues until the node 
  is either less than its parent or it is the root.
\end{frame}

\subsubsection{Heap Delete Min/Max}
Notice that the min/max is always at the top of the heap, so it is
quite easy to remove.  However, the after removal the heap is no
longer valid.  The solution is to move the last element in the tree to
the now empty root, and then fix the heap by percolating down.

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Heaps: Percolate Down}}
  To \emph{percolate down}, we check to see if a node is greater than it's
  children.  if it is not, we swap it with the smaller of the two
  children.  This process continues until the node is either greater
  than its children or it is a leaf.
\end{frame}

\subsubsection{Other Operations}

Decrease key:
\begin{itemize}
   \item Max heap: percolate down
   \item Min heap: percolate up
\end{itemize}

Increase key:
\begin{itemize}
   \item Max heap: percolate up
   \item Min heap: percolate down
\end{itemize}

Delete:
\begin{itemize}
   \item In min heap, decrease to smallest priority then remove min
\end{itemize}

\subsection{Implementing a Heap}
As shown on pages 548 and 549 of your text book, an array is often
used to implement a heap.

\subsection{Java Implementation}
Remember that most of the data structures that we have seen so far in
the Java collections framework are defined by some sort of interface
(that is, an abstract definition) and then there are one or more
implementation of the interface (think of the list interface: we have
a Linked List implementation and an Array List implementation).  For
better or for worse, (probably for worse), there is not such interface
for the Priority Queue.  There is, however, one implementation.  
You can view
\href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html}{the API here}.

%\mode<all>{\bibliography{sources}}

\end{document}
